/*
 * @lc app=leetcode.cn id=436 lang=java
 *
 * [436] 寻找右区间
 */

// @lc code=start

import java.util.Arrays;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        // 索引数组
        Integer[] index = new Integer[n];
        for(int i = 0; i < n; i++) {
            index[i] = i;
        }

        // 按照区间的起点排序
        Arrays.sort(index, (a, b) -> intervals[a][0] - intervals[b][0]);

        int[] res = new int[n];
        for(int i = 0; i < n; i++) {
            int end = intervals[i][1];
            int right = binarySearch(intervals, index, end);
            int idx = index[right];
            res[i] = intervals[idx][0] >= end ? idx : -1;
        }
        
        return res;
    }

    public int binarySearch(int[][] intervals, Integer[] index, int target) {
        int left = 0, right = index.length - 1;

        while(left < right) {
            int mid = left + (right - left) / 2;

            if(intervals[index[mid]][0] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
// @lc code=end

